// https://leetcode.cn/problems/verifying-an-alien-dictionary/
// Created by ade on 2022/8/22.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    // 小于排序
    bool isAlienSorted(vector <string> &words, string order) {
        int orderArr[26];
        int k = 0;
        for (auto c :order) {
            orderArr[c - 'a'] = k;
            k++;
        }
        for (int i = 0; i < words.size() - 1; i++) {
            int len1 = words[i].size();
            int len2 = words[i + 1].size();
            int len = min(len1, len2);
            int j = 0;
            for (; j < len; j++) {
                if (orderArr[words[i][j] - 'a'] < orderArr[words[i + 1][j] - 'a']) {
                    // 代表已经小于了，不用后续比较了
                    break;
                }
                if (orderArr[words[i][j] - 'a'] > orderArr[words[i + 1][j] - 'a']) {
                    return false;
                }
            }
            if (j == len && len1 > len2) {
                return false;
            }

        }
        return true;
    }
};

int main() {
    Solution so;
    vector <string> s = {"apple", "appl"};
    string order = "abcdefghijklmnopqrstuvwxyz";
    auto a = so.isAlienSorted(s, order);
    cout << a << endl;
    return 0;
}